package top100;

import java.util.HashMap;

/**
 * @author Godc
 * @description
 */
public class LRU {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(2,1);
        lruCache.put(2,2);
        lruCache.get(2);
        lruCache.put(1,4);
        lruCache.put(4,1);
        lruCache.get(2);
    }
}
class LRUCache {
    class DoubleLinkedListNode{
        int key;
        int val;
        DoubleLinkedListNode pre;
        DoubleLinkedListNode next;
        public DoubleLinkedListNode(){};
        public DoubleLinkedListNode(int key,int val){this.key = key;
        this.val = val;}
    }
    private HashMap<Integer,DoubleLinkedListNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DoubleLinkedListNode head,tail;
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DoubleLinkedListNode();
        tail = new DoubleLinkedListNode();
        head.next = tail;
        tail.pre = head;
    }
    public int get(int key) {
        DoubleLinkedListNode node = cache.get(key);
        if(node==null) return -1;
        removeToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        DoubleLinkedListNode node = new DoubleLinkedListNode(key,value);
        if(cache.containsKey(key)){
            // 删除原节点，插入到头部,并重新更新状态
            deleteNode(cache.get(key));
            addToHead(node);
            cache.put(key,node);
        }else{
            if(cache.size()==capacity){
                // 删除链表尾部的数据，并且将map中的对应节点给删除
                DoubleLinkedListNode removeNode = removeTail();
                cache.remove(removeNode.key);
            }
            // 插入到链表头部，并在map中构建映射
            addToHead(node);
            cache.put(key,node);
        }
    }
    public  void addToHead(DoubleLinkedListNode node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }
    public void addToTail(DoubleLinkedListNode node){
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
    }
    public void deleteNode(DoubleLinkedListNode node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }
    public void removeToHead(DoubleLinkedListNode node){
        deleteNode(node);
        addToHead(node);
    }
    public DoubleLinkedListNode removeTail(){
        DoubleLinkedListNode node = tail.pre;
        deleteNode(node);
        return node;
    }


}
